學習資源

https://labuladong.online/algo/data-structure-basic/linkedlist-basic/#双链表的基本操作

學習記錄

今天是學習的第 4 天，主要學習了雙鏈表的基本操作：

單鏈表和雙鏈表之間的差異

單鏈表

• 每個節點只有一個指針 next，指向下一個節點
• 只能單向遍歷（從頭到尾）

雙鏈表

• 每個節點有兩個指針：next 指向下一個節點，prev 指向前一個節點
• 可以雙向遍歷（從頭到尾或從尾到頭）

這邊是一個工具函式，用來創建雙鏈表

function DoublyListNode(x) {
  this.val = x;
  this.next = this.prev = null;
}

var createDoublyLinkedList = function(arr) {
  if (arr === null || arr.length === 0) {
    return null;
  }

  var head = new DoublyListNode(arr[0]);
  var cur = head;

  // for 循環迭代創建雙鏈表
  for (var i = 1; i < arr.length; i++) {
    var newNode = new DoublyListNode(arr[i]);
    cur.next = newNode;
    newNode.prev = cur;
    cur = cur.next;
  }

  return head;
}

查 / 改

雙鏈表的遍歷 / 查找 / 修改

對於雙鏈表的遍歷和查找，可以從頭節點或尾節點開始：

// 創建一條雙鏈表
var head = createDoublyLinkedList([1, 2, 3, 4, 5]);
var tail = null;

// 從頭節點向後遍歷雙鏈表
for (var p = head; p !== null; p = p.next) {
    console.log(p.val);
    tail = p;
}

// 從尾節點向前遍歷雙鏈表
for (var p = tail; p !== null; p = p.prev) {
    console.log(p.val);
}

增

情況一：在雙鏈表頭部插入新元素

在雙鏈表頭部插入元素，需要調整新節點和原頭節點的指針：

// 創建一條雙鏈表
var head = createDoublyLinkedList([1, 2, 3, 4, 5]);

// 在雙鏈表頭部插入新節點 0
var newHead = new DoublyListNode(0);
newHead.next = head;
head.prev = newHead;
head = newHead;
// 現在鏈表變成了 0 -> 1 -> 2 -> 3 -> 4 -> 5

情況二：在雙鏈表尾部插入新元素

在雙鏈表尾部插入元素時，如果我們有尾節點的引用，這個操作會非常簡單：

// 創建一條雙鏈表
var head = createDoublyLinkedList([1, 2, 3, 4, 5]);

var tail = head;
// 先走到鏈表的最後一個節點
while (tail.next !== null) {
    tail = tail.next;
}

// 在雙鏈表尾部插入新節點 6
var newNode = new DoublyListNode(6);
tail.next = newNode;
newNode.prev = tail;
// 更新尾節點引用
tail = newNode;

// 現在鏈表變成了 1 -> 2 -> 3 -> 4 -> 5 -> 6

情況三：在雙鏈表中間插入新元素

在雙鏈表的指定位置插入新元素，需要調整前驅節點和後繼節點的指針。

// 創建一條雙鏈表
var head = createDoublyLinkedList([1, 2, 3, 4, 5]);

// 想要插入到索引 3（第 4 個節點）
// 需要操作索引 2（第 3 個節點）的指針
var p = head;
for (var i = 0; i < 2; i++) {
    p = p.next;
}

// 組裝新節點
var newNode = new DoublyListNode(66);
newNode.next = p.next;
newNode.prev = p;

// 插入新節點
p.next.prev = newNode;
p.next = newNode;

// 現在鏈表變成了 1 -> 2 -> 3 -> 66 -> 4 -> 5

刪

情況一：在雙鏈表中間刪除一個節點

在雙鏈表中刪除節點時，需要調整前驅節點和後繼節點的指針來摘除目標節點：

// 創建一條雙鏈表
var head = createDoublyLinkedList([1, 2, 3, 4, 5]);

// 刪除第 4 個節點
// 先找到第 3 個節點
var p = head;
for (var i = 0; i < 2; i++) {
    p = p.next;
}

// 現在 p 指向第 3 個節點，我們把它後面那個節點摘除出去
var toDelete = p.next;

// 把 toDelete 從鏈表中摘除
p.next = toDelete.next;
toDelete.next.prev = p;

// 把 toDelete 的前後指針都設為 null 是個好習慣（可選）
toDelete.next = null;
toDelete.prev = null;

// 現在鏈表變成了 1 -> 2 -> 3 -> 5

情況二：在雙鏈表頭部刪除一個元素

在雙鏈表頭部刪除元素需要調整頭節點的指針：

// 創建一條雙鏈表
var head = createDoublyLinkedList([1, 2, 3, 4, 5]);

// 刪除頭節點
var toDelete = head;
head = head.next;
head.prev = null;

// 清理已刪除節點的指針
toDelete.next = null;

// 現在鏈表變成了 2 -> 3 -> 4 -> 5

情況三：在雙鏈表尾部刪除一個元素

在單鏈表中，由於缺乏前驅指針，所以刪除尾節點時需要遍歷到倒數第二個節點，操作它的 next 指針，才能把尾節點摘除出去。

但在雙鏈表中，由於每個節點都儲存了前驅節點的指針，所以我們可以直接操作尾節點，把它自己從鏈表中摘除：

// 創建一條雙鏈表
var head = createDoublyLinkedList([1, 2, 3, 4, 5]);

// 刪除尾節點
var p = head;
// 找到尾節點
while (p.next !== null) {
    p = p.next;
}

// 現在 p 指向尾節點
// 把尾節點從鏈表中摘除
p.prev.next = null;

// 把被刪除節點的指針都斷開是個好習慣（可選）
p.prev = null;

// 現在鏈表變成了 1 -> 2 -> 3 -> 4

學習總結

• 單鏈表只有一個指針 next，指向下一個節點
• 雙鏈表有兩個指針：next 指向下一個節點，prev 指向前一個節點
• 雙鏈表可以雙向遍歷
• 當要操作雙鏈表中間的某個節點時，需要找到其前驅節點